As a part of the normal integrated circuit (IC) design process, a consistency check of the physical layout of each layer of the IC, including metal layers, semiconductor layers, and the like, is normally performed on the IC design database to detect and correct any mistakes in the design. One of the checks typically performed on such a database is ensuring two adjacent rectangular portions of a layer, such as two metal connections of an IC metal layer, do not overlap. Such a condition often results in two separate circuits of the IC being inadvertently connected together, thus causing improper operation of the IC. Such database checks ordinarily must be performed many thousands of times for each IC due to the large number of transistors and other circuit components normally found in today's integrated circuit technologies. As a result, the amount of time required for each single operation of checking for overlap between two rectangles can significantly influence the overall time required to perform such a check on an entire IC design database.
Typically, checking for possible overlap of two rectangles is performed by iterating over the entire area of each of the rectangles in small sections to determine if any two such sections, one from each of the two rectangles, reside in the same area of the IC layer surface. Such iterations are necessarily time-consuming, causing an inordinate amount of computer processing time to be expended for that particular task.
Alternately, the boundaries of the two rectangles may be determined, and then each line segment defining the boundary of one rectangle may be compared against each line segment of the other rectangle in order to determine if any line segments of opposite rectangles intersect. Additionally, a check must be made to determine if one of the rectangles resides completely within the other, as no line segments of the two rectangles will intersect in that particular case, thereby reducing the usefulness of a simple line intersection check. Although this particular method is likely to be less computationally intensive than the iterative method, a significant amount of computing time is required nonetheless.
From the foregoing, a need exists for a faster method for detecting if two rectangular features of an electronic design structure, such as an IC metal or semiconductor layer, overlap. Such a method would significantly reduce the time required to check each pair of rectangles, thus reducing overall IC design time.